Information processing is performed in all fields in the present society. This information processing is performed by the use of arithmetic units such as computers. Various pieces of data are calculated and processed to obtain meaningful results. By doing so, prediction, determination, control, and the like are performed. One field of this information processing is an optimization process and the optimization process is an important field. The problem of finding a solution which minimizes resources or costs needed for performing a process, the problem of finding a solution which maximizes a result obtained by performing a process, and the like are known. It is clear that these problems are very important.
Linear programming is a typical optimization problem. With linear programming, a vector of variables which maximize or minimize an evaluation function represented by the linear sum of plural continuous variables under restrictive conditions represented by linear sums is found. Linear programming is used in various fields such as a product production plan. With linear programming, excellent algorithms, such as a simplex method or interior point methods, are known. Even a problem including hundreds of thousands or more of variables is efficiently solved.
On the other hand, many optimization problems in which variables have not continuous values but discrete values are known. For example, a traveling salesman problem in which the shortest path at the time of going the rounds of plural cities in turn and making a return is found or a knapsack problem in which a combination that maximizes the sum of the value of different articles put in a knapsack is found is known. These problems are referred to as a discrete optimization problem, a combinatorial optimization problem, or the like. With these problems it is known that it is very difficult to obtain an optimum solution.
The major cause of difficulty in solving a discrete optimization problem is as follows. Because each variable has only a discrete value, the technique of reaching an optimum solution by continuously changing a variable so as to improve an evaluation function is not usable. Furthermore, in addition to a value of each variable (optimum solution, a global solution, or a global minimum) by which an optimum solution is obtained, there are a great many solutions (minimal (maximal) solutions, local solutions, or local minimums) by which the extreme value of an evaluation function is locally obtained. Accordingly, in order to reliably obtain an optimum solution, it is inevitable that an algorithm, such as substituting a value for each variable one by one, will be adopted. This leads to a very long calculation time. Discrete optimization problems include many problems for which it is expected that calculation time taken to find an optimum solution exponentially increases with respect to the size of a problem (that is to say, the number of variables). These problems are referred to as non-deterministic polynomial (NP)-hard problems in computational complexity theory. The above traveling salesman problem and knapsack problem are NP-hard problems.
As stated above, it is very hard to reliably find an optimum solution of a discrete optimization problem. Accordingly, with a discrete optimization problem which is practically important, an algorithm using a property inherent in the problem is devised. As stated above, with many discrete optimization problems it is expected that calculation time taken to obtain an exact solution exponentially increases. Therefore, many practical solutions are approximate solutions. An optimum solution is not obtained, but a solution by which a value of an evaluation function is approximate to an optimum value is obtained.
Not only these approximation algorithms specializing in individual problems but also approximation algorithms which may handle a wide range of problems because of solving them without using their properties are known. The latter approximation algorithms are referred to as metaheuristics. A simulated annealing (SA) method, a genetic algorithm, a neural network, and the like are metaheuristics. These metaheuristics may be inefficient compared with an algorithm which properly uses the property of a problem. With these metaheuristics, however, it is expected to obtain a solution at a high speed compared with an algorithm by which an exact solution is obtained.
The present disclosure relates to a simulated annealing method.
A simulated annealing method is a type of Monte Carlo method and stochastically finds a solution by the use of random numbers. Description will now be given with the problem of minimizing a value of an evaluation function to be optimized as an example. A value of an evaluation function will be referred to as energy. In the case of maximization, a sign of an evaluation function should be changed.
The beginning is an initial state in which one discrete value is substituted for each variable. A state (state in which a value of only one variable is changed, for example) close to the current state (combination of values of variables) is selected and the state transition from the current state to the selected state is discussed. A change in energy caused by that state transition is calculated. Whether to adopt that state transition and make a change in state or to keep the original state without adopting that state transition is stochastically determined according to a calculated value. If an adoption probability at the time of a decrease in the energy is larger than an adoption probability at the time of an increase in the energy, then it is expected that on average, a change in state occurs in a direction in which the energy decreases and that a state transition to a more suitable state is made with time. Finally, an optimum solution or an approximate solution by which an energy close to an optimum value is obtained may be obtained. If adoption and non-adoption are deterministically performed in the case of a decrease and an increase, respectively, in the energy, then a change in the energy decreases with respect to time. However, if the state reaches a local minimum, no further change occurs. As stated above, with a discrete optimization problem there are a great many local minimums. As a result, it is approximately certain that a state is trapped into a local minimum not very close to an optimum value. Therefore, it is important to stochastically determine whether to perform adoption.
With simulated annealing, it is proved that a state reaches an optimum solution at a limit at which time (the number of iterations) is infinite by determining an adoption (allowance) probability of a state transition in the following way.
(1) An energy change (energy decrease) value associated with a state transition is −ΔE. An allowance probability p of the state transition is determined by one of the following functions f(x):
                              p          ⁡                      (                                          Δ                ⁢                                                                  ⁢                E                            ,              T                        )                          =                  f          ⁡                      (                                          -                Δ                            ⁢                                                          ⁢                              E                /                T                                      )                                              (                  1          ⁢                      -                    ⁢          1                )                                                      f            metro                    ⁡                      (            x            )                          =                              min            ⁡                          (                              1                ,                                  e                  x                                            )                                ⁢                      (                          METROPOLIS              ⁢                                                          ⁢              METHOD                        )                                              (                  1          ⁢                      -                    ⁢          2                )                                                      f            Gibbs                    ⁡                      (            x            )                          =                              1                          1              +                              e                                  -                  x                                                              ⁢                      (                          GIBBS              ⁢                                                          ⁢              METHOD                        )                                              (                  1          ⁢                      -                    ⁢          3                )            where T is a parameter referred to as a temperature and is changed in the following way.
(2) The temperature T is lowered logarithmically in accordance with
                    T        =                                            T              0                        ⁢                          log              ⁡                              (                c                )                                                          log            ⁡                          (                              t                +                c                            )                                                          (        2        )            where t is the number of iterations and T0 is an initial temperature. It is desirable to set T0 to a sufficiently large value according to a problem.
It is assumed that an allowance probability given by the expression in (1) is used and that a steady state is reached after a sufficient number of iterations. Then an occupation probability of each state follows Boltzmann distribution in a thermal equilibrium state in the thermodynamics. When a temperature is gradually lowered from a high value, an occupation probability of a low energy state increases. Therefore, when a temperature is sufficiently lowered, the lowest energy state will be obtained. This is very similar to a change in state which occurs at the annealing of a material. Accordingly, this method is referred to as a simulated annealing method. At this time a state transition by which energy increases occurs stochastically. This corresponds to thermal excitation in the physics.
As stated above, with a simulated annealing method an optimum solution is obtained by setting an infinite number of iterations. In reality, however, there is a need to obtain a solution by setting a finite number of iterations. Therefore, it is impossible to reliably find an optimum solution. Furthermore, according to the above expression, temperature lowers very slowly. As a result, temperature does not sufficiently lower in a finite time. Accordingly, with an actual simulated annealing method, temperature does not change logarithmically. That is to say, in many cases, temperature is lowered more quickly.
FIG. 13 illustrates the schematic structure of an optimization apparatus based on a simulated annealing method. The following description includes a case where a plurality of candidate state transitions are generated. With an original basic simulated annealing method, however, one candidate state transition is generated at a time.
First an optimization apparatus 10 includes a state holding section 11 which holds a current state S (values of plural state variables). Furthermore, the optimization apparatus 10 includes an energy calculation section 12. When one of the values of the plural state variables changes, a state transition from the current state S occurs. The energy calculation section 12 calculates an energy change {−ΔEi} for each state transition. The optimization apparatus 10 also includes a temperature control section 13 which controls a temperature T and a transition control section 14 which controls a change in state.
On the basis of a temperature T, energy changes {−ΔEi}, and random numbers, the transition control section stochastically generates at most one state transition according to relative relationships between the energy changes {−ΔEi} and thermal excitation energies.
The transition control section 14 is subdivided further. That is to say, the transition control section 14 includes a candidate generator 14a which generates candidate state transitions and a transition assessor 14b which stochastically determines from an energy change {−ΔEi} and a temperature T whether to allow a corresponding candidate state transition. Furthermore, the transition control section 14 includes a transition determiner 14c which selects a candidate state transition to be adopted from among allowed candidate state transitions and a random number generator 14d which generates random numbers.
The following operation is performed in one iteration. First the candidate generator 14a generates one or more candidate state transitions (candidate number {Ni}) from the current state S held in the state holding section 11 to a next state. The energy calculation section calculates an energy change {−ΔEi} for each candidate state transition by the use of the current state S and the candidate state transition. The transition assessor 14b uses a temperature T generated by the temperature control section 13 and a random variable (random number) generated by the random number generator 14d to determine, according to an energy change {−ΔEi} for each candidate state transition, whether to allow the candidate state transition with an allowance probability given by the expression in the above (1). Furthermore, the transition assessor 14b outputs the propriety {fi} of each candidate state transition. If there are a plurality of allowed candidate state transitions, then the transition determiner 14c selects one of them at random by the use of a random number. In addition, the transition determiner 14c outputs a transition number N and a transition propriety f of the selected state transition. If there is an allowed candidate state transition, then a value of a state variable stored in the state holding section 11 is updated according to the adopted state transition.
The operation is started from an initial state. At the same time that a temperature is being lowered by the temperature control section 13, the above iteration is repeated. When the end determination condition that the number of iterations reaches a certain number, the end determination condition that energy falls below a certain value, or the like is met, the operation ends. A solution outputted by the optimization apparatus 10 is a state at end time. In reality, however, a temperature does not become zero if the number of iterations is finite. Accordingly, even at the end time an occupation probability of a state has distribution represented by Boltzmann distribution or the like. An optimum value or a good solution is not always obtained. That is to say, a realistic solution is to hold the lowest energy state obtained until then in the course of an iteration and to output it at the end.
FIG. 14 is a circuit-level block diagram illustrative of an example of the structure of a calculation part needed for a transition control section, more particularly for a transition assessor based on ordinary simulated annealing which generates one candidate state transition at a time.
A transition control section 14 includes a random number generation circuit 14b1, a selector 14b2, a noise table 14b3, a multiplier 14b4, and a comparator 14b5.
The selector 14b2 selects an energy change {−ΔEi} corresponding to a transition number N which is a random number generated by the random number generation circuit 14b1 from among energy changes {−ΔEi} calculated for candidate state transitions and outputs it.
The function of the noise table 14b3 will be described later. For example, a memory, such as a random access memory (RAM) or a flash memory, is used as the noise table 14b3.
The multiplier 14b4 outputs the product (corresponding to the above thermal excitation energy) of a value outputted by the noise table 14b3 and a temperature T.
The comparator 14b5 outputs as a transition propriety f a comparison result obtained by comparing a multiplication result outputted by the multiplier 14b4 and −ΔE which is an energy change selected by the selector 14b2.
The transition control section 14 illustrated in FIG. 14 basically has the above function. However, a mechanism for allowing a state transition with an allowance probability given by the expression in (1) is not yet described. This mechanism will now be described.
A circuit which outputs 1 with an allowance probability of p and which outputs 0 with an allowance probability of (1−p) is realized in the following way. A comparator having two inputs A and B is used. When A>B, the comparator outputs 1. When A<B, the comparator outputs 0. An allowance probability of p is inputted to the input A. A uniform random number having a value in the interval [0, 1) is inputted to the input B. Therefore, by inputting to the input A of this comparator a value of an allowance probability p calculated by the use of the expression in (1) on the basis of an energy change and a temperature T, the above function is realized.
That is to say, it is assumed that f is the function used in the expression in (1) and that u is a uniform random number having a value in the interval [0, 1). Then the above function is realized by a circuit which outputs 1 when f(ΔE/T) is greater than u.
The above function is realized in this way. By making the following modification, however, the same function is also realized. Even if the same monotone increasing function is made to operate on two numbers, the magnitude relationship between them does not change. Therefore, even if the same monotonically increasing function is made to operate on two inputs of a comparator, its output does not change. If f−1 which is an inverse function of f is adopted as this monotonically increasing function, a circuit which outputs 1 when −ΔE/T is greater than f−1(u) may be used. Furthermore, a temperature T is positive. Therefore, a circuit which outputs 1 when −ΔE is greater than Tf−1(u) may be used. The noise table 14b3 illustrated in FIG. 14 is a conversion table for realizing the inverse function f−1(u) and outputs values of the following functions for an input obtained by discretizing the interval [0, 1):
                                          f            metro                          -              1                                ⁡                      (            u            )                          =                  log          ⁡                      (            u            )                                              (                  3          ⁢                      -                    ⁢          1                )                                                      f            Gibbs                          -              1                                ⁡                      (            u            )                          =                  log          ⁡                      (                          u                              1                -                u                                      )                                              (                  3          ⁢                      -                    ⁢          2                )            
The transition control section 14 also includes a latch which holds a determination result and the like, a state machine which generates that timing, and the like. For the sake of simplicity, however, these are not illustrated in FIG. 14.
FIG. 15 illustrates the flow of the operation of the transition control section 14 based on conventional simulated annealing. The flow of the operation includes a step (S1) in which one state transition is selected as a candidate, a step (S2) in which the propriety of the state transition is determined by comparing an energy change for the state transition and the product of a temperature and a random number, and a step (S3) in which the state transition is adopted if the state transition is allowed and in which the state transition is not adopted if the state transition is not allowed.
As will be imagined in some degree from the above description, a simulated annealing method is widely used and is very attractive. However, because there is need to slowly lower temperature, calculation time is comparatively long. Furthermore, it is hard to properly adjust according to a problem how to lower temperature. This will be described in the following way by the use of FIG. 16.
There are many local minimums whose approximation degrees are low along a state transition path from an initial state to an optimum solution or good approximate solutions. In order to escape from these local minimums sufficiently quickly, a high temperature which enables sufficient thermal excitation is needed. However, an energy spread in Boltzmann distribution is wide at a high temperature. Therefore, the difference in occupation probability between an optimum solution or good approximate solutions whose energy is low (hereinafter referred to as a good solution) and a local minimum whose energy is comparatively high and whose approximation degree is low (hereinafter referred to as a bad solution) is small. Accordingly, even if a quick escape from a local minimum is made, destinations are dispersed to many bad solutions and the probability that a good solution will be reached is very small. In order to increase an occupation probability of a good solution, a low temperature at which thermal excitation energy is sufficiently low compared with the difference in energy between the good solution and a bad solution is needed. In this case, however, thermal excitation energy is low. As a result, the probability of going beyond a peak of energy along the path is very low and a change in state hardly occurs. Therefore, there is need to gradually increase an occupation probability of a good solution by slowly going through an intermediate temperature at which it is possible in some degree to go beyond a peak of energy and at which there is a little difference in occupation probability. If temperature is lowered too slowly, it does not fall appreciably in finite time. As a result, an occupation probability of a good solution does not finally increase. Conversely, if temperature is lowered too quickly, it falls before an escape from a local minimum is made. As a result, a state remains trapped into a bad solution. Therefore, as temperature falls, the rate of a change in the temperature is made sufficiently small. There is need to substantially wait until Boltzmann distribution at the temperature is approached.
As has been described, with the original simulated annealing, an escape from a local minimum is made only by thermal excitation based on temperature. Accordingly, there is need to slowly lower temperature. Furthermore, there is need to properly adjust according to a problem how to lower temperature.
The problem of being trapped into a local minimum may be alleviated by a method other than temperature adjustment. A temperature control method or an evaluation function is dynamically changed (see, for example, Japanese Laid-open Patent Publication No. 06-19507 or Japanese Laid-open Patent Publication No. 09-34951). A method for generating a neighbor which is a state transition destination is dynamically changed (see, for example, Japanese Laid-open Patent Publication No. 10-293756). With these methods, a search is conducted in a wide range during the early stages of calculation and a search is conducted with high accuracy in a narrow range in the last stage of calculation. By doing so, calculation time is reduced.
With these methods, for example, plural functions are dynamically replaced or statistics are collected to grasp the progress of a search. That is to say, comparatively complex calculations are needed. It is desirable to reduce calculation time by a simpler general-purpose method.
As stated above, with the simulated annealing method it takes a long time to escape from a local minimum. This is the main cause of a long calculation time. Therefore, if there is a method which promotes an escape from a local minimum, it is expected that calculation time is significantly reduced. However, simply escaping from a local minimum does not always reduce calculation time. As stated above, there are a great many bad solutions. Therefore, even if an escape from a local minimum is made at random, a state is simply trapped again into a surrounding bad solution. Not a simple escape but an escape for making a state transition to a better state is desirable.
There is a hint about an escape for proceeding in a good direction in the convergence theorem of the above simulated annealing method. This theorem indicates determining the propriety of a state transition in accordance with a state transition probability of the Metropolis method or the Gibbs method leads to proceeding in a good direction.
At a local minimum, a state transition probability is very small. Accordingly, a candidate state transition is selected many times. The branching ratio of state transitions after that is proportional to a state transition probability of the Metropolis method or the Gibbs method. Therefore, if the absolute values of allowance probabilities of state transitions are increased with the relative ratio of the allowance probabilities maintained, then the branching ratio of the state transitions is maintained. This makes it possible to reduce the length of a stay at a local minimum without exerting a bad influence upon convergence. As a result, calculation time is reduced.
A problem to be solved in the present disclosure is to obtain means to promote an escape from a local minimum without dynamically changing an evaluation function, a state transition generation method, or the like or marring convergence. More specifically, a problem to be solved in the present disclosure is to obtain means to increase the absolute values of allowance probabilities of state transitions at a local minimum are increased with the relative ratio of the allowance probabilities maintained.
H. Zhu et al., “A Boltzmann Machine with Non-rejective Move”, IEICE Transactions on Fundamentals vol. E85-A, No. 6. pp. 1229-1235, June 2002 is one of these means. There are errors in the description of this literature. However, the above problem is solved by making suitable corrections. This means is as follows. Allowance probabilities of all state transitions are calculated. When the maximum ratio of an allowance probability to a random number having exponential distribution is obtained, this allowance probability is adopted. This makes it possible to select a state transition to be adopted at a rate proportional to an original allowance probability. With this means, the relative ratio of allowance probabilities is maintained and the probability of staying in an original state is zero. Therefore, this means is very effective. However, an increase in computational complexity is caused by calculating an allowance probability and generating a random number.